package trees;

public class IsBTSTree {
    /**
     * BST:二叉搜索树（Binary Search Tree）
     * 在一颗二叉树中，任意节点的值要大于等于左子树所有节点的值，且要小于等于右子树的值
     */

    public boolean isValidBST(TreeNode node) {
        return isValidBST(node, null, null);
    }

    public boolean isValidBST(TreeNode node, TreeNode min, TreeNode max) {
        if (node == null) return true;

        if (min != null && node.val <= min.val) return false;

        if (max != null && node.val >= max.val) return false;

        return isValidBST(node.left, min, node) && isValidBST(node.right, node, max);
    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(5);
        node.left = new TreeNode(2);
        node.right = new TreeNode(6);

        node.left.left = new TreeNode(1);
        node.left.right = new TreeNode(4);

        node.right.right = new TreeNode(7);

        node.left.right.left = new TreeNode(3);
        node.preTraverse(node);
        System.out.println();

        IsBTSTree bts = new IsBTSTree();
        boolean isBTS = bts.isValidBST(node);
        System.out.println("is BTS? " + isBTS);
    }
}
